package datastructure.graph.无向图;

/**
 * 连通分量
 * @author MaoLin Wang
 * @description
 * @date 2020/8/27 3:17 下午
 */
public class CC {
    private boolean[] marked;
    private int[] id;
    private int[] size;
    private int count;

    public CC(Graph graph) {
        marked=new boolean[graph.getV()];
        id=new int[graph.getV()];
        size=new int[graph.getV()];
        for (int i = 0; i < graph.getV(); i++) {
            if (!marked[i]){
                dfs(graph,i);
                count++;
            }
        }
    }

    private void dfs(Graph graph, int v) {
        id[v]=count;
        size[count]++;
        marked[v]=true;
        for (Integer w : graph.adj(v)) {
            if (!marked[w]){
                dfs(graph,w);
            }
        }
    }

    public boolean isMarked(int v) {
        return marked[v];
    }

    public int id(int v) {
        return id[v];
    }

    public int[] getSize() {
        return size;
    }

    public int getCount() {
        return count;
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 2);
        graph.addEdge(0, 1);
        graph.addEdge(2, 1);
        graph.addEdge(2, 3);
        graph.addEdge(3, 1);
        graph.addEdge(5,4);
        CC cc=new CC(graph);
        System.out.println(cc.getCount());
    }
}
